There are two basic trends in conflict with each other with regards to video streaming. The first trend is that users are watching more and more streaming video on their mobile devices. The “Cisco Visual Networking Index: Global and North America Mobile Data Traffic Forecast Update” for 2013-2018 predicts that by 2018, the average mobile user across the globe will exceed 3 GB of data usage each month, up from 356 MB in 2013, and almost 70% of the data usage will be from video alone.
The second trend is that mobile network carriers, in order to build and maintain a high-speed network capable of catering to this increasing data hunger, are increasingly utilizing tiered or usage-based pricing schemes, with significant penalties for overages.
Users, ISPs, and content providers (CP) all have interests in handling this conflict. Users desire to stop worrying about monthly data plans and watch all the videos they want with minimal distortion. An ISP may desire to either (a) reduce data traffic to lower network congestion and thereby operational and capital expenditure costs, or (b) preserve traffic to continue receiving fees from customers and/or content providers. And CPs have three potential desires: (a) allows a user to access more content under the same data plan, and in so doing, achieve greater profit for the CP by increasing advertising revenue; (b) CPs can market a solution as a competitive advantage over other CPs; and (c) doing so reduces the potential need for the CP to pay the ISP for the customer's data charges.
There are two main approaches to handling this conflict between the two trends. The first approach is to force, or at least default to, the use of low-quality video at all times for mobile users. This is the solution chosen for the YouTube mobile app, as well as by Netflix for Canadian mobile users, but low quality video may be of such low quality that it is barely tolerable. The second approach is to provide a warning when users near or reach their data usage limit, which leads to unsatisfied users, as they likely will still incur large overage charges. Therefore, to prevent unsatisfied users, bitrates must be optimized across an entire billing cycle.
This optimization problem is known as the Multiple-Choice Knapsack Problem (MCKP). In the regular single-choice knapsack problem, a set of items is given, each with an associated value and weight. The objective is to pick a subset of the items such that the total value is maximized while not exceeding the knapsack capacity. In the stream selection problem, the items are the individual bit rate versions of the videos, and the multiple choices arise because exactly one version of each video must be selected.
For a video request arriving at time t, a decision vector xt=(xt1, . . . , xtM) is defined, where each xtj takes the value 1 if bit rate version j is chosen, and 0 otherwise. Then the problem is:maximize Σt=1TΣj=1Mutjxtj, subject toΣt=1TΣj=1Mctjxtj≦B and Σj=1Mxtj=1, ∀t, with variables xtjε{0,1}, ∀t,j   (1)
where the first constraint says that the cost of the selected bit rates for all the videos requested in a billing cycle must not exceed the quota B, and the second constraint says that one bit rate version may be selected for each video.
The traditional offline version of the MCKP, where all the input items are known in advance, is well studied. The problem is NP-hard, but pseudo-polynomial time dynamic programming (DP) solutions exist. The offline algorithm solves problem (1) with the knowledge of all future video requests. It achieves the best possible performance and is treated as the benchmark against which the performance of any online algorithm must be measured. This is called the hindsight offline optimal algorithm.
Contrary to this offline theoretical version, any actual system that optimizes bit rates of streaming videos does not know the video requests in advance, and so needs to make decisions in an online fashion. This requires a modification to the formulation to handle online requests.
Zhou et al. presents an online algorithm to solve (1) regardless of the sequence of video requests. This is called the online MCKP algorithm. The MCKP algorithm uses relatively little information, needing only the maximum and minimum utility-to-cost ratio across all requested videos, and an estimate of the sum data of the smallest bit rates. The MCKP algorithm does not use prediction or time deadlines, but requires only the quota.
Because of this, however, the MCKP algorithm optimizes for the worst-case performance, rather than expected performance. Therefore, its performance is often suboptimal. A system that allows a user to view videos at a near-optimal video quality across an entire billing period for any given user without exceeding the user's bandwidth quota is therefore desirable.